Grokking Meta Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Meta Easy Problems
Toeplitz Matrix (easy)
Solution: Toeplitz Matrix
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Island Perimeter (easy)
Solution: Island Perimeter
Moving Average from Data Stream (easy)
Solution: Moving Average from Data Stream
Move Zeroes (easy)
Solution: Move Zeroes
Missing Ranges (easy)
Solution: Missing Ranges
Palindrome Permutation (easy)
Solution: Palindrome Permutation
Rank Transform of an Array (easy)
Solution: Rank Transform of an Array
Meta Medium Problems
Diagonal Traverse (medium)
Solution: Diagonal Traverse
Shortest Path in Binary Matrix (medium)
Solution: Shortest Path in Binary Matrix
Maximum Swap (medium)
Solution: Maximum Swap
Custom Sort String (medium)
Solution: Custom Sort String
Binary Tree Vertical Order Traversal (medium)
Solution: Binary Tree Vertical Order Traversal
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Basic Calculator II (medium)
Solution: Basic Calculator II
Nested List Weight Sum (medium)
Solution: Nested List Weight Sum
Dot Product of Two Sparse Vectors (medium)
Solution: Dot Product of Two Sparse Vectors
Max Consecutive Ones III (medium)
Solution: Max Consecutive Ones III
Subarray Sum Equals K (medium)
Solution: Subarray Sum Equals K
Next Permutation (medium)
Solution: Next Permutation
Simplify Path (medium)
Solution: Simplify Path
Lowest Common Ancestor of a Binary Search Tree (medium)
Solution: Lowest Common Ancestor of a Binary Search Tree
'K' Closest Points to the Origin (medium)
Solution: 'K' Closest Points to the Origin
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Merge Intervals (medium)
Solution: Merge Intervals
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Number of Islands (medium)
Solution: Number of Islands
Clone Graph (medium)
Solution: Clone Graph
Missing Element in Sorted Array (medium)
Solution: Missing Element in Sorted Array
Number of Substrings Containing All Three Characters (medium)
Solution: Number of Substrings Containing All Three Characters
Capacity To Ship Packages Within D Days (medium)
Solution: Capacity To Ship Packages Within D Days
Count and Say (medium)
Solution: Count and Say
Contiguous Array (medium)
Solution: Contiguous Array
Meta Hard Problems
Sliding Window Median (hard)
Solution: Sliding Window Median
Alien Dictionary (hard)
Solution: Alien Dictionary
Minimum Window Substring (hard)
Solution: Minimum Window Substring
Best Meeting Point (hard)
Solution: Best Meeting Point
Maximum Sum of 3 Non-Overlapping Subarrays (hard)
Solution: Maximum Sum of 3 Non-Overlapping Subarrays
Making A Large Island (hard)
Solution: Making A Large Island
Basic Calculator (Hard)
Solution: Basic Calculator
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Longest Increasing Path in a Matrix (hard)
Solution: Longest Increasing Path in a Matrix
Valid Palindrome III (hard)
Solution: Valid Palindrome III
Solution: Basic Calculator

Problem Statement

Given a string s, representing the arithmetic expressions, evaluate the expression and return the resultant value.

Constraints:

  • s contains digits, '+', '-', '(', ')', and ' '.
  • '+' is used as addition operation but not as a unary operator. (i.e., "+2" and "+(1 + 3)" is invalid).
  • '-' is used as a unary and subtraction operator both. (i.e., "-2" and "-(1 + 3)" is valid).

Note: You are not allowed to use the built-in function like eval() to evaluate the mathematical expression.

Examples

  • Example 1:

    • Input: "3 - (2 - 1) + 4"
    • Expected Output: 6
    • Justification: The expression inside the parentheses 2 - 1 evaluates to 1. So the expression becomes 3 - 1 + 4, which sums up to 6.
  • Example 2:

    • Input: "10 + (8 - (4 + 2)) - 1"
    • Expected Output: 11
    • Justification: Inside the inner parentheses, 4 + 2 equals 6. The expression becomes 10 + (8 - 6) - 1. Then 8 - 6 equals 2, so it simplifies to 10 + 2 - 1, which is 11.
  • Example 3:

    • Input: "5 + (3 - (2 + (8 - 5)) + 7) - (6 - 4)"
    • Expected Output: 8
    • Justification: In the innermost parentheses, 8 - 5 equals 3. The expression becomes 5 + (3 - (2 + 3) + 7) - (6 - 4). The next inner expression 2 + 3 equals 5, so it becomes 5 + (3 - 5 + 7) - 2. Simplifying further to 5 + 5 - 2, we get 10 - 2, which is 8.

Solution

To solve this problem, we utilize a stack-based approach to handle the precedence imposed by parentheses and to perform the calculations. This method is effective as stacks allow us to manage the order of operations and operands in a controlled manner.

Initially, we iterate through the expression, handling digits, operators, and parentheses separately. For digits, we construct numbers; for operators, we manage the current operation; and for parentheses, we use the stack to preserve the state of the calculation. When we encounter an open parenthesis, we push the current result and the sign onto the stack and reset them for the new inner expression. Upon encountering a closing parenthesis, we pop from the stack to restore the state and combine it with the current result. This method ensures that we maintain the correct order of operations and handle nested expressions effectively.

Step-by-Step Algorithm

  1. Initialize Variables:

    • Create a result variable to store the cumulative result of the expression.
    • Define a number variable to build numbers as they are read from the string.
    • Set a sign variable to +1 or -1, indicating the current sign (positive or negative) for the number being processed.
    • Initialize a stack to handle parentheses in the expression.
  2. Iterate Over the String:

    • Loop through each character in the input string.
  3. Process Each Character:

    • If the character is a digit:
      • Update number by multiplying the current number by 10 and adding the new digit. This step builds multi-digit numbers from consecutive digits in the string.
    • If the character is a '+' or '-':
      • Apply the previous sign to the current number and add it to result.
      • Reset number to 0.
      • Update sign based on whether the character is '+' (set sign to 1) or '-' (set sign to -1).
    • If the character is an opening parenthesis '(':
      • Push the current result and sign onto the stack. This step saves the current state before processing the expression inside the parentheses.
      • Reset result to 0 and sign to 1 to start calculating the expression inside the parentheses.
    • If the character is a closing parenthesis ')':
      • First, add the current number to result after applying the current sign.
      • Then, the expression inside the parentheses is complete. Pop the last sign from the stack and multiply it with the current result.
      • Pop the last saved result from the stack and add it to the current result.
      • Reset number to 0.
  4. Final Calculation:

    • After the loop, there might be a number that hasn't been added to the result. Add this number to result after applying the last sign.
  5. Return Result:

    • Return the final result, which is the evaluation of the entire arithmetic expression.

5. Algorithm Walkthrough

Let's use the input "5 + (3 - (2 + (8 - 5)) + 7) - (6 - 4)":

  1. Initialize Variables:

    • result = 0, number = 0, sign = 1, stack = [].
  2. Process Each Character:

    • '5': number = 5.
    • '+': result = 0 + (5 * 1) = 5, number = 0, sign = 1, stack = [].
    • '(': push result (5) and sign (1) to stack, stack = [5, 1], reset result = 0 and sign = 1.
    • '3': number = 3.
    • '-': result = 0 + (3 * 1) = 3, number = 0, sign = -1, stack = [5, 1].
    • '(': push result (3) and sign (-1) to stack, stack = [5, 1, 3, -1], reset result = 0 and sign = 1.
    • '2': number = 2.
    • '+': result = 0 + (2 * 1) = 2, number = 0, sign = 1, stack = [5, 1, 3, -1].
    • '(': push result (2) and sign (1) to stack, stack = [5, 1, 3, -1, 2, 1], reset result = 0 and sign = 1.
    • '8': number = 8.
    • '-': result = 0 + (8 * 1) = 8, number = 0, sign = -1, stack = [5, 1, 3, -1, 2, 1].
    • '5': number = 5.
    • ')': result = 8 + (5 * -1) = 3, result *= stack.pop() (1) = 3, result += stack.pop() (2) = 5, number = 0, stack = [5, 1, 3, -1].
    • ')': result *= stack.pop() (-1) = -5, result += stack.pop() (3) = -2, number = 0, stack = [5, 1]``.
    • '+': sign = 1.
    • '7': number = 7.
    • ')': result = -2 + (7 * 1) = 5, result *= stack.pop() (1) = 5, result += stack.pop() (5) = 10, number = 0, stack = [].
    • '-': sign = -1.
    • '(': push result (10) and sign (-1) to stack, stack = [10, -1], reset result = 0 and sign = 1.
    • '6': number = 6.
    • '-': result = 0 + (6 * 1) = 6, number = 0, sign = -1, .
    • '4': number = 4.
    • ')': result = 6 + (4 * -1) = 2, result *= stack.pop() (-1) = -2, result += stack.pop() (10) = 8, number = 0, stack = [].
    • Final Calculation: The final result after the loop is 8.
  3. Return Result:

    • The final result is 8.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string. This is because each character in the string is processed exactly once.
  • Space Complexity: O(n), in the worst case, due to the stack used to handle parentheses. In the worst case, the stack's size is proportional to the number of parentheses, which can be as large as the length of the string.
Basic Calculator (Hard)
Serialize and Deserialize Binary Tree (hard)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

  1. Algorithm Walkthrough

Code

Complexity Analysis